<head>
    <meta charset="UTF-8">
<title>算法训练 Airport Configuration</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>问题描述</p>
<p>ACM机场是一个本地机场，对于大多数人来说，机场不是他们的终点或起点，而是中转站。机场有一个规划图。到达的大门在机场的北边（相当于空格）。出发的大门在机场的南边（也相当于空格）。两个正对着的大门距离相当于大门间的距离。每一个到达的大门只对应一个城市。每一个出发的大门也是这样。乘客到达的大门对应他们的起始城市，而出发大门对应他们的目标城市。因为这个问题，我们只需考虑转机的乘客。</p>
<div>转机的乘客会产生机场的交通堵塞。我们已经知道某两个城市之间的平均客流量。用这些信息，有可能能降低交通堵塞。例如，Cx城到Cy城的客流量大，就可以将他们安排得很近，甚至是对位。</div>
<div>因为花园和商店无法穿越，所以到达门G1和出发们G3（见图）的距离为1+2=3。</div>
<div>你需要计算几个方案的客流指数。两个大门间的客流指数等于人数乘以距离。而总的客流指数就是所有门之间的客流指数之和。</div>
<div>&nbsp;</div>
<div>&nbsp;</div>
<div>&nbsp;</div>
<div><img src="http://lx.lanqiao.cn/RequireFile.do?fid=bhT7f62F" width="784" height="386" alt="" /></div>
<p>输入格式</p>
<p>输入文件有多组测试数据。</p>
<p>最后一组只有一个0。</p>
<p>每组测试数据的输入有两部分。先是客流数据，之后是机场布局。</p>
<p>数据开始时一个n(1&lt;n&lt;25)，表示城市数。接下来n行，每行表示一个城市的数据，第i行先是一个整数，表示起始城市，再一个1到n的整数k，表示目标城市数，k对整数，每对描述一个目标城市，第一个数是城市编号j，然后是乘客数目(最多500)从i到j的人数。</p>
<p>机场布局部分包括1到20个方案。用一个0结束。</p>
<p>一个方案包括3行。第一行一个数表示编号，第二行是1-n的一个排列，描述到达门对应的城市的排列，第三行用同样的方式描述出发大门。</p>
<p>输出格式</p>
<p>对于每个测试数据，输出包括一个表格，表示方案编号和客流指数，按照客流指数升序输出。若客流指数相同，则编号小的排在前面。见样例。注意方案编号右对齐，而客流指数左对齐。（样例输出前面4个空格，后面9个空格，然后没有空格，详见未格式化的试题。</p>
<p>样例输入</p>
<p>&nbsp;3</p>
<p>1  2  2 10  3 15</p>
<p>2  1  3 10</p>
<p>3  2  1 12  2 20</p>
<p>1</p>
<p>1 2 3</p>
<p>2 3 1</p>
<p>2</p>
<p>2 3 1</p>
<p>3 2 1</p>
<p>0</p>
<p>2</p>
<p>1&nbsp;1  2 100</p>
<p>2  1  1&nbsp;200</p>
<p>1</p>
<p>1 2</p>
<p>1 2</p>
<p>2</p>
<p>1 2</p>
<p>2 1</p>
<p>0</p>
<p>0</p>
<p>样例输出</p>
<p>Configuration Load</p>
<p>&nbsp; &nbsp; 2 &nbsp; &nbsp; &nbsp; &nbsp; 119 &nbsp; &nbsp; &nbsp; &nbsp;</p>
<p>&nbsp; &nbsp; 1 &nbsp; &nbsp; &nbsp; &nbsp; 122</p>
<p>Configuration Load</p>
<p>&nbsp; &nbsp; 2 &nbsp; &nbsp; &nbsp; &nbsp; 300 &nbsp; &nbsp; &nbsp; &nbsp;</p>
<p>&nbsp; &nbsp; 1 &nbsp; &nbsp; &nbsp; &nbsp; 600</p>
<p>&nbsp;</p>